The present invention is related generally to nonsinusoidal spread spectrum radio communication systems, and more particularly to signal acquisition by nonsinusoidal spread spectrum radio transceivers.
In contrast with traditional sinusoidal-carrier radio communication systems where the transmitted electromagnetic power is concentrated in a narrow frequency band, in spread spectrum communication systems the power is distributed over a relatively large bandwidth. Spread spectrum radio communications are used in place of traditional systems to circumvent communications jamming by interference signals, prevent detection and interception by unwanted receivers so as to provide privacy, provide tolerance to multipath transmissions, send multiple independent signals over a frequency band, and/or provide accurate ranging information.
Nonsinusoidal spread spectrum (NSS) transmissions a(t) relevant to the present invention are of the form
a(t)=xcexa8(t)*d(t),xe2x80x83xe2x80x83(1.1)
where t is time, d(t) is a data function with data values of positive and negative unity where the data values of the data function d(t) have a bit width ts, and xcexa8(t) is a pseudorandom code sequence consisting of a repeated series of a pseudorandom code "PHgr"(t) of length ts, i.e.,
xcexa8(t)="PHgr"(t mod ts),xe2x80x83xe2x80x83(1.2)
where the pseudorandom code "PHgr"(t) has a value of zero for t less than 0 and t greater than ts. The data function d(t) changes value at integer multiples of ts, and one bit of data from d(t) is therefore encoded on each repetition of the pseudorandom code "PHgr"(t).
An exemplary NSS transmission a(t) based on a pseudorandom code "PHgr"(t) having a length of seven bits is shown in FIG. 1A. The first five bits of the data function d(t) are (1, xe2x88x921, 1, 1, xe2x88x921, . . . ) and the pseudorandom code "PHgr"(t) consists of the bits (1, 1, 1, xe2x88x921, 1, xe2x88x921, xe2x88x921). Therefore, as shown in FIG. 1A, the product of the data function d(t) and the pseudorandom code sequence xcexa8(t), which consists of bits (1, 1, 1, xe2x88x921, 1, xe2x88x921, xe2x88x921, 1, 1, 1, xe2x88x921, 1, xe2x88x921, xe2x88x921, . . . ), is the transmission a(t) consisting of bits (1, 1, 1, xe2x88x921, 1, xe2x88x921, xe2x88x921, xe2x88x921, xe2x88x921, xe2x88x921, 1, xe2x88x921, 1, 1, 1, 1, 1, xe2x88x921, 1, xe2x88x921, xe2x88x921, 1, 1, 1, xe2x88x921, 1, xe2x88x921, xe2x88x921, . . . ).
The cross-correlation xcex9(t) between a first function A(t) and a second function B(t) is given by                                           Λ                          A              ,              B                                ⁢                      xe2x80x83                    ⁢                      (            t            )                          =                              ∫                          -              ∞                        ∞                    ⁢                      A            ⁢                          xe2x80x83                        ⁢                          (                              τ                -                t                            )                        *            B            ⁢                          xe2x80x83                        ⁢                          (              τ              )                        ⁢                          xe2x80x83                        ⁢                                          ⅆ                τ                            .                                                          (        1.3        )            
When the first function A is the same as the second function B, the above equation provides the autocorrelation xcex9A(t), i.e.,                                           Λ            A                    ⁢                      xe2x80x83                    ⁢                      (            t            )                          =                              ∫                          -              ∞                        ∞                    ⁢                      A            ⁢                          xe2x80x83                        ⁢                          (                              τ                -                t                            )                        *            A            ⁢                          xe2x80x83                        ⁢                          (              τ              )                        ⁢                          xe2x80x83                        ⁢                                          ⅆ                τ                            .                                                          (        1.4        )            
If the first function A(t) and the second function B(t) are both periodic with period T, then the cross-correlation xcex9A,B(t) and the autocorrelation xcex9A also are periodic with period T, i.e.,
xcex9A,B(t)=xcex9A,B(t mod T),xe2x80x83xe2x80x83(1.5)
and
xcex9A(t)=xcex9A(t mod T).xe2x80x83xe2x80x83(1.6)
Therefore, if the first and second functions A(t) and B(t) have period T, the integration used to determine the correlation function may be performed over a time t of length T and then normalized, and the starting time for an integration over a time t of length T is immaterial.
If the functions A(t) and B(t) are actually bit sequences xcex1(i) and xcex2(i) of length N bits, with each bit having a bit length of xcex94t, then
xe2x80x83xcex9A,B(nxcex94t)=xcfx80xcex1xcex2(n)xcex94t,xe2x80x83xe2x80x83(1.7)
where xcexxcex1xcex2 is the discrete cross-correlation given by                                                         λ                              α                ,                β                                      ⁢                          xe2x80x83                        ⁢                          (              n              )                                =                                    ∑                              i                =                1                            N                        ⁢                          xe2x80x83                        ⁢                          α              ⁢                              xe2x80x83                            ⁢                              (                                  i                  -                  n                                )                            *              β              ⁢                              xe2x80x83                            ⁢                              (                i                )                                                    ,                            (        1.8        )            
where i and n are integers. Similarly, if the function A(t) is a bit sequence xcex1(i) of length N, with each bit having a bit length of xcex94t, then
xcex9A(nxcex94t)=xcexxcex1(n)xcex94t,xe2x80x83xe2x80x83(1.9)
where xcexxcex1 is the discrete autocorrelation given by                                           λ            α                    ⁢                      xe2x80x83                    ⁢                      (            n            )                          =                              ∑                          i              =              1                        N                    ⁢                      xe2x80x83                    ⁢                      α            ⁢                          xe2x80x83                        ⁢                          (                              i                -                n                            )                        *            α            ⁢                          xe2x80x83                        ⁢                                          (                i                )                            .                                                          (        1.10        )            
For example, consider the discrete autocorrelation xcexxcex1 for the five-bit sequence xcex1={1, xe2x88x921, xe2x88x921, 1, xe2x88x921}. For instance, the n=1 value of the discrete autocorrelation xcexxcex1 is calculated by
xcexxcex1(1)=xcex1(0)xcex1(1)+xcex1(1)xcex1(2)+xcex1(2)xcex1(3)+xcex1(3)xcex1(4)+xcex1(4)xcex1(5)=xe2x88x921 xe2x88x921+xe2x88x921xe2x88x921=xe2x88x923.xe2x80x83xe2x80x83(1.11)
As can be shown by similar such calculations, the discrete autocorrelation xcexxcex1 has values of 5, xe2x88x923, 1, 1 and xe2x88x923 for n equals 0, 1, 2, 3 and 4, respectively. As shown in FIG. 2, the continuous autocorrelation xcexxcex94 for the corresponding function xcex94(t) is easily generated from the discrete autocorrelation xcexxcex1 by connecting autocorrelation values at integer multiples of xcex94t by straight lines. It should also be noted that the continuous autocorrelation xcex9A is symmetric about t=0, and, of course, periodic with a period of T=5xcex94t.
A fundamental class of binary sequences which have useful autocorrelation properties is the maximal sequence class. Any maximal sequence may be generated by a linear feedback shift register (LFSR). (It is important to note that the binary bit values of unity and negative unity, which will be used in the present specification when discussing correlations and autocorrelations, may be directly translated to the binary bit values of zero and unity, which will be used in the present specification when discussing the operation of LFSR""s and generating polynomials.) The exemplary LFSR 100 shown in FIG. 3A is a five-stage shift register consisting, from right to left, of five flip-flops 101, 102, 103, 104, and 105. (In the present specification the convention will be that for LFSRs with an output on the right, the rightmost flip-flop will be referred to as the first flip-flop, the second-from-the-right flip-flop will be referred to as the second flip-flop, etc. For instance, the leftmost flip-flop 105 will be referred to as the fifth flip-flop 105.) On each clock pulse, the bit value held in each of the four leftmost flip-flops 102, 103, 104 and 105 of the LFSR 100 is shifted one flip-flop to the right. (A clock and its connections within the LFSR 100 are not shown in FIG. 3A.) Therefore, on a clock pulse the bit value in the fifth flip-flop 105 is shifted into the fourth flip-flop 104, the bit value in the fourth flip-flop 104 is shifted into the third flip-flop 103, etc. The output 111 of the LFSR 100 is produced by the first flip-flop 101. The input value to the fifth flip-flop 105 of the LFSR 100 is provided by a feedback loop 110 which, in the case of this particular LFSR 100, consists of an XOR adder 121 which taps the output 113 of the third flip-flop 103, as well as the output 111 of the first flip-flop 101. (Although the exemplary LFSR 100 of FIG. 3A has only a single XOR adder 121 in the feedback loop 110, it should be understood that, in general, an LFSR may direct taps from the outputs of any of its flip-flops to additional XOR adders in the feedback loop.) The XOR addition, which is typically notated as xe2x80x98⊕xe2x80x99, of two binary value inputs is equal to unity when one, and only one, of the binary value inputs is unity, and is zero otherwise, i.e., 0⊕0=0; 0⊕1=1; 1⊕1=1; and 1⊕1=0. This type of flip-flop configuration, with taps from the outputs of some or all of the flip-flops to XORs in a feedback loop (the output of the first flip-flop is necessarily directed to the feedback loop), which is summed and directed to the leftmost flip-flop, is known as a Fibonacci construction LFSR.
For instance, if xe2x80x98seedxe2x80x99 values of {0, 0, 1, 1, 1} are placed in the flip-flops 105, 104, 103, 102 and 101, respectively, then on the next clock pulse the fourth, third, second and first flip-flops 104, 103, 102 and 101 receive the bit values of 0, 0, 1, 1, respectively. The XOR 121 receives the outputs of the first and third flip-flops 101 and 103, and therefore produces an output of zero which is sent to the fifth flip-flop 105. Therefore, the new state of the LFSR is {0, 0, 0, 1, 1}. Similarly, on the next clock pulse the fourth, third, second and first flip-flops 104, 103, 102 and 101 receive the bit values of 0, 0, 0, 1, respectively. The XOR 121 receives the outputs of the first and third flip-flops 101 and 103, and therefore produces an output of unity which is sent to the fifth flip-flop 105. Therefore, the new state of the LFSR is {1, 0, 0, 0, 1}. As can be seen from Table 1, which provides a list of the first ten states and outputs produced by the seed of {0, 0, 1, 1, 1}, the output values from this seed are (1, 1, 1, 0, 0, 0, 1, 1, 0, 1, . . . ).
Transitions between states of an LFSR may be represented as arrows in a state transition diagram, where the states of the LFSR may be depicted on a linear or a circular axis. A state transition diagram 150 for an n-stage LFSR is shown in FIG. 3D on a circular axis 151 where the state (2nxe2x88x921) is located adjacent to state 0. For a Fibonacci LFSR in state X, there are only two possibilities for the next state. Either (a) a zero can be output from the LFSR and put into the most significant bit, in which case the state becomes └X/2┘, or (b) a one can be output from the LFSR and put into the most significant bit, in which case the state becomes (2nxe2x88x921+└X/2┘), where the partial brackets xe2x80x9c└ ┘xe2x80x9d indicate that the greatest integer less than or equal to the value inside the partial brackets is taken. The transition from state X to state └X/2┘ is represented by an arrow 155 which begins at X and ends approximately halfway between X and 0. The transition from state X to state (2nxe2x88x921+└X/2┘) is represented by an arced arrow 157 which begins at X and ends diametrically opposite state └X/2┘, ie., the end of the arced arrow 157 is located where arrow 155 sums with arrow 156 which spans the diameter of the circular axis 151. Similarly, the transition from state Y, which has a value somewhat greater than 2nxe2x88x921, to state └Y/2┘ is represented by an arrow 165 beginning at Y and ending approximately halfway between Y and 0, and the transition from state Y to state (2nxe2x88x921+└Y/2┘) is represented by an arced arrow 167 which begins at Y and ends diametrically opposite state └Y/2┘.
A mirror image version 110xe2x80x2 of the LFSR 100 of FIG. 3A, is shown in FIG. 3B. Although it may seem trivial that the mirror image LFSR 100xe2x80x2 functions in exactly the same way as the LFSR 100 of FIG. 3A, due to frequent confusions found in the literature it is important to point out that the xe2x80x9cmost significant bitxe2x80x9d is held in the leftmost flip-flop 105 of the LFSR 100 of FIG. 3A, while the xe2x80x9cmost significant bitxe2x80x9d in the mirror-image LFSR 100xe2x80x2 of FIG. 3B is in the rightmost flip-flop 105.
A different type of construction for a five-stage shift register 200 is shown in FIG. 3C. As shown in FIG. 3C, the output 201 from the first flip-flop 201, i.e., the rightmost flip-flop 201, is fed via lead 223 to an XOR adder 233 located between the fourth flip-flop 204 and the third flip-flop 203. The XOR adder 233 also receives the output 214a of the fourth flip-flop 204, and the output 214b of the XOR 233 is directed to the third flip-flop 203. This type of construction, where one or more XOR adders are located in the signal path between the series of flip-flops is known as a Galois construction LFSR. (Again we point out, motivated by confusions found in the literature, that a mirror-image version of the Galois LFSR 200 of FIG. 3C functions exactly as the LFSR 200 of FIG. 3C. Furthermore, the most significant bit is held in the leftmost flip-flop 205 of the LFSR 200 of FIG. 3C, and in the mirror-image version the most significant bit would be held in the rightmost flip-flop.)
Galois construction LFSRs have the advantage of being faster than Fibonacci construction, because the computations required for a Fibonacci construction LFSR will generally have to propagate through more levels of logic, and may therefore require a longer clock cycle. It may be shown that any Fibonacci construction LFSR may be mapped to a Galois construction LFSR which can generate the same sequence of output values. This mapping between Fibonacci and Galois constructions is accomplished by reversal of the ordering of the taps/feeds. For instance, the Galois construction LFSR 200 of FIG. 3C is equivalent to the Fibonacci construction LFSR 100 of FIG. 3A, since the Galois construction LFSR 200 is five flip-flops in length and has a feed to an XOR 233 between the fourth flip-flop 204 and the third flip-flop 203, and the Fibonacci construction LFSR 100 is five flip-flops in length and has a feed to an XOR 121 between the third flip-flop 102 and the second flip-flop 103. Therefore, in general, a Fibonacci LFSR of n flip-flops with m taps from the inputs to the t1, t2, . . . , tm flip-flops is equivalent to a Galois LFSR of n flip-flops with m feeds to XOR adders following the (nxe2x88x92t1), (nxe2x88x92t2), . . . , (nxe2x88x92tm) flip-flops.
The equivalence of the LFSRs 100 and 200 of FIGS. 3A and 3C can be verified by noting that both LFSRs 100 and 200 produce the same periodic output. For instance, if flip-flops 205, 204, 203, 202 and 201 of FIG. 3B have the seed values {1, 1, 1, 1, 1}, respectively, then on the first clock pulse the output 201 of the LFSR 210 is unity, and this value of unity is deposited in the fifth flip-flop 205. Similarly, the fourth, second and first flip-flops 204, 202 and 201 receive the values of unity from the fifth, third and second flip-flops 205, 203 and 202, respectively. The XOR 233 receives the value of unity from the fourth flip-flop 204 and the value of unity from the first flip-flop 201, and so the XOR 233 feeds a value of zero to the third flip-flop 203. Therefore, the new state of the flip-flops 201-205 is {1, 1, 0, 1, 1}. By the same process described above it is easily verified that the next set of values in the LFSR 200 is {1, 1, 0, 0, 1}. Table 2 below provides a list of the first ten states of the LFSR 200, showing that both LFSRs 110 and 210 do indeed have the same output values. As can be seen from Table 1, which provides a list of the first ten states and outputs produced by the seed of {0, 0, 1, 1, 1}, the output values from this seed match the series of output values from listed in Table 1 above.
For certain feedback configurations of Galois or Fibonacci LFSRs, which are termed optimal configurations, the states of the flip-flops of an LFSR cycle through all possible combinations, except the zero state, i.e., {0, 0, 0, . . . , 0}. The zero state cannot be included in the sequence of states, because upon the next clock pulse the LFSR remains in the zero state, so all outputs of the LFSR are zero, and the output sequence as well as the sequence of states of the flip-flops have a period of unity. Therefore, for an optimal configuration LFSR of n flip-flops, the output has a period N of 2nxe2x88x921 which consists of 2n/2xe2x88x921 values of zero and 2n/2 values of unity. Such an output is termed a maximal sequence. The LFSRs 100 and 100xe2x80x2 of FIGS. 3A and 3B are examples of optimal configurations.
Just as Fibonacci-configuration LFSRs can be mapped to Galois-configuration LFSRs and vice versa, it may be shown that each LFSR which generates a maximal sequence can be mapped to a Galois field of order 2n. Elements of the Galois field of order 2n are n-tuples of binary digits which can also be represented as polynomials of degree (nxe2x88x921) with all coefficients being either zero or unity. For instance, the element (1, 0, 0, 1, 1) corresponds to the polynomial
1xc2x7x4+0xc2x7x3+0xc2x7x2+1xc2x7x1+1xc2x7x0=x4+x+1.xe2x80x83xe2x80x83(2.1)
Multiplication in the Galois field is defined as a multiplication of the corresponding polynomials (with coefficients obeying modulo 2 arithmetic) from which the remainder is taken modulo an irreducible polynomial, i.e., a polynomial with no polynomial factors, of degree n. (See, for example, chapter 25 of Number Theory in Science and Communication, Second Edition, M. R. Schroeder, Springer-Verlag, Berlin, 1986.) Using this definition of multiplication, the elements of the Galois field are generated by a primitive element xcex6. That is, the elements of the Galois field are
0, xcex61, xcex62, xcex63, . . . xcex6q(n)xe2x88x922, xcex6q(n)xe2x88x921,xe2x80x83xe2x80x83(2.2)
where q(n)=2n. If the irreducible polynomial used to define the multiplication operation is written as
h(x)=h0xn+h1xnxe2x88x921+ . . . +hnxe2x88x921x+hn,xe2x80x83xe2x80x83(2.3)
where h0=hn=1, then it can be shown that the most significant bits of the sequence of fields xcex61, xcex62, xcex63, . . . xcex6q(n)xe2x88x922, xcex6q(n)xe2x88x921 is a maximal sequence (u1, u2. u3, . . . uq(n)xe2x88x921) given by
uj=h1ujxe2x88x921⊕h2 ujxe2x88x922⊕ . . . , ⊕hnxe2x88x921ujxe2x88x92n+1⊕hnujxe2x88x92n.xe2x80x83xe2x80x83(2.4)
By comparing this functional form to the exemplary Fibonacci LFSR 100 of FIG. 3A it can be seen that this is equivalent to the sequence generated by the LFSR 100 when hi=1 if the ith cell from the left has its output fed back to the input 105 of the LFSR 100, and hi=0 if the ith cell from the left does not have its output fed back to the input 105 of the LFSR 100. In the case of the LFSR 100 of FIG. 3A, equation (2.4) becomes
xe2x80x83uj=ujxe2x88x923⊕ujxe2x88x925,xe2x80x83xe2x80x83(2.5)
and the fifth-order polynomial corresponding to equation (2.5) is
h(x)=1xc2x7x5+0xc2x7x4+0xc2x7x3+1xc2x7x2+0xc2x7x1+1=x5+x2+1.xe2x80x83xe2x80x83(2.6)
The polynomial of equation (2.6) may be written as (1, 0, 0, 1, 0 1), or, even more conveniently, in octal notation as (45o). (It should be noted that although the five-bit LFSR 100 corresponds to a fifth-order polynomial, the octal representation of the polynomial consists of six bits. Therefore, in this case, according to the terminology of the present specification, the five-bit LFSR 100 has a six-bit octal representation.) According to an analogous notation, the locations of feeds for the Galois LFSR 200 of FIG. 3C is written as (1, 0, 1, 0, 0, 1), or (51)o, where the subscript xe2x80x98Oxe2x80x99 indicates an octal number. A primitive polynomial is a polynomial of the form of equation (2.3) that generates a maximal sequence.
A list of all maximal sequences generated by two-bit through sixteen-bit shift registers (i.e., three-bit through seventeen-bit octal representations) is provided as a microfiched appendix to the present specification. The polynomials for the maximal sequences provided in octal Galois form are followed by an xe2x80x9cogxe2x80x9d, and the polynomials for the maximal sequences provided in octal Fibonacci form are followed by an xe2x80x9cofxe2x80x9d. For instance, a maximal sequence for a four-bit Galois-configuration shift register can be produced by the (31)o polynomial or the (23)o polynomial. As may be verified by inspection of the primitive polynomials provided in the microfiched appendix to the present specification., the number of configurations which produce maximal sequences for an n-bit shift register is given by
xcfx86(2nxe2x88x921)/nxe2x80x83xe2x80x83(2.7)
where xcfx86(i) is Euler""s totient function which has a value equal to the number of integers which are less than i and have no common divisors with i. For instance, if n=4, then (2nxe2x88x921)=15, and there are eight integers, namely 1, 2, 4, 6, 7, 8, 11, and 13, which have no common divisors with 15. Therefore, as the microfiched appendix confirms, there are only two (Fibonacci or Galois) polynomials which generate maximal sequences for four-bit LFSRs. Pages 53-54 of the present specification provides C-language programming code for generating the set of all maximal sequences for an n-bit shift register.
The sequences generated by LFSRs are cyclic, i.e., if {u1, u2, . . . , uN} is a sequence generated by equation (2.3), then {umod(N, 1+i), umod(N, 2+i), . . . , umod(N, N+i)} is also a sequence generated by equation (2.3) for any integer i. Therefore, the starting point of a sequence is arbitrary. The sequence {umod(N, 1+i), umod(N, 2+i), . . . , umod(N, N+i)} is a phase shift of magnitude i of the sequence {u1, u2, . . . , uN}, and this is written as
{umod(N, 1+i), umod(N, 2+i), . . . , umod(N, N+i)}=Pi{u1, u2, . . . , uN},xe2x80x83xe2x80x83(2.8)
where P is the phase shift operator.
Generally, families of pseudorandom code sequences which have low cross-correlations and sharply peaked autocorrelations are used in NSS communications. Using these types of code sequences, reception of an NSS transmission a(t) is accomplished by circuitry which calculates the correlation between the received signal a(t) and the expected pseudorandom code sequence "PHgr"(t). To receive the transmission a(t), the transmitted pseudorandom code sequence and the time of its arrival must be known or determined by the receiver. When a receiver calculates the correlation between an incoming signal and an internally-generated signal consisting of the same code sequence and beginning at the time of arrival of the incoming signal, the relatively large value of the calculated correlation indicates that a transmission was indeed received. With low cross-correlations, the communications between one pair of transceivers using one pseudorandom sequence will not interfere with the communications of other transceivers in the vicinity which are using other pseudorandom code sequences.
A maximal sequence has the useful property that its autocorrelation is very sharply peaked. For zero phase shift, the discrete autocorrelation of a maximal sequence has a value of 2nxe2x88x921, and for all other (bit length) phase shifts the discrete autocorrelation has a value of xe2x88x921. However, the cross-correlation properties of maximal sequences are poor, i.e., the cross-correlation values are not small. (See xe2x80x9cCrosscorrelation Properties of Pseudorandom and Related Sequences,xe2x80x9d Dilip V. Sarwate and Michael B. Pursley, Proceedings of the IEEE, Vol. 68, No. 5, May 1980, page. 602, column 1.)
Many types of spread spectrum systems have transceivers which transmit continuous signals and also continually receive incoming signals. In contrast, as specified in detail in U.S. Pat. No. 6,002,708 for Spread Spectrum Localizers, which is incorporated herein by reference, according to the present invention the transmissions of the transceivers are episodic, i.e., not continuous. (According to the terminology of the present specification, an xe2x80x9cepisodicxe2x80x9d transmission may be periodic, i.e., it may consist of one or more transmissions within a period, as long as there are intervals of non-transmission between the transmissions.) According to the present invention, the reception of an episodic transmission a(t) consists of a sequence of operations including: (i) a sequence generator produces an internally-generated integration sequence xcex1i(t) which resembles the expected pseudorandom sequence xcex1e(t) of the received signal a(t); (ii) a set of event registers is armed to trigger reception processing circuitry bracketing a finite time interval during which a reception is expected to occur; (iii) during the reception event the received signal a(t) is multiplied by internally-generated integration sequences xcex1i(t) which are delayed by a number of different time offsets; and (iv) the correlations of the delayed internally-generated integration sequences xcex1i(t) and the received signal a(t) are calculated and analyzed. As specified in detail in U.S. Pat. No. 6,002,708, the correlations are calculated using a time-integrating correlator circuit. Although the time-integrating correlator output resembles a time sampling of the correlation xcex9xcex1,a(t) between the internally-generated integration sequence xcex1i(t) and the received signal a(t), it should be noted that the correlation as a function of time is never actually determined by the time-integrating correlator circuit, and therefore it cannot be sampled. The time-integrating correlation circuit only determines values of discrete correlation function xcexxcex1,a(n) at a number of discrete times, which are referred to as the time bins. If the time bins are separated by an interval of ts seconds, the time-integrating correlator circuit has M integrators, and each time bin has a length of tx seconds, then the length of the time window during which the time-integrating correlator can detect a signal during a reception event is [(Mxe2x88x921)*ts+tx].
However, before a pair of transceivers can begin communications, both transceivers must first determine that the other transceiver is broadcasting from within a distance where reception is possible. The transmissions and attempted receptions that occur up until either of the transceivers actually receives a signal from the other is termed the contact stage of the acquisition process. Once the two transceivers have determined that there is another transceiver in the vicinity, then the two transceivers enter the synchronization stage of the acquisition process where they must synchronize their transmission/reception schedules and arrange any other protocols required for continued communications. Two transceivers involved in the acquisition process are referred to as the acquiring transceivers. Furthermore, transceivers which are not involved in the acquisition process are referred to as nonacquiring transceivers.
An exemplary group of transceivers 30A, 30B, 30C, 30D, 30E, 30F and 30G in various levels of communication is shown in FIG. 1B. Transceivers 30A, 30B, 30C and 30D have already completed the acquisition stage with each of the other transceivers 30A, 30B, 30C and 30D within that group, and are involved in two-way communications 40AB, 40AC, 40AD, 40BC, 40BD, 40CD with each other. (The bi-directionality of the communications 40AB, 40AC, 40AD, 40BC, 40BD, 40CD is illustrated by the arrows at each end of the line segments.) Transceivers 30D and 30E are involved in a two-way communication 40DE with each other, but transceiver 30E is not in communication with any of the other transceivers 30A, 30B, 30C, 30D, 30F and 30G. If transceiver 30E is to begin communications with the other transceivers 30A, 30B, 30C which transceiver 30D is in communication with, synchronization information regarding the other transceivers 30A, 30B, 30C may be communicated to transceiver 30E via communications with transceiver 30D. Alternatively, synchronization of transceiver 30E with any of the other transceivers 30A, 30B, 30C, 30D, 30F and 30G may be accomplished by an acquisition process where transceiver 30E locates a beacon signal broadcast by the other transceivers 30A, 30B, 30C, 30D, 30F and 30G, or vice versa. Transceivers 30C and 30G are involved in a one-way communication 40CG with each other where transceiver 30G has located the beacon signal of transceiver 30C, but transceiver 30C has not located the beacon signal of transceiver 30G and so transceiver 30C is not yet aware of the existence of transceiver 30G. Transceiver 30G may possibly be involved in more accurately determining the schedule of beacon transmissions from transceiver 30C, or may have already completed that process. Since transceiver 30G has located the beacon signal of transceiver 30C, transceiver 30G has timing information regarding transceiver 30C, and to complete the acquisition process transceiver 30G can broadcast a beacon signal when transceiver 30C will be attempting to receive beacon signals. Transceiver 30F is not in communication with any other transceivers 30A, 30B, 30C, 30D, 30E and 30G in the group. However, transceiver 30F is broadcasting beacon signals and attempting to receive beacon signals. Furthermore, all the transceivers 30A, 30B, 30C, 30D, 30E, 30F and 30G (which will generically be assigned the reference numeral 30) have recurrent periods of time during which they listen for beacon signals to determine if transceivers 30 which they are not currently in contact with have come into communication range. It may be physically impossible, due to the finite transmission power of the transceivers 30, for all transceivers 30 to be in direct contact with each other. However, information may be passed from transceivers 30 to transceiver 30, so that transceivers 30 which are beyond the range of direct communications may communicate indirectly.
Typically, beacon signals within a prearranged family of codes are used for acquisition. However, according to the preferred embodiment of the present invention, a single prearranged beacon sequence is used for acquisition. As an example of a system that does not provide the advantages of the present invention, consider the acquisition process for a transmitter which is broadcasting a beacon signal 300 which consists of beacon packets 310 of length tb seconds once every tc seconds, as is shown in FIG. 4A, where each beacon packet 310 is a maximal sequence. If the maximal sequences 310 each have a bit length of N then, as shown in FIG. 4B, the central peak 350 of the autocorrelation function xcex9xcex1345 for these beacon packets 310 has a magnitude of N and a width of roughly tb/N, and in the regions 360 outside the peak 350 the value of the autocorrelation function xcex9xcex1345 is considerably smaller than the peak value N. (As is shown in FIG. 4B and discussed in more detail below in conjunction with FIGS. 9A-9C, because of the random nature of the bit values in a maximal sequence, the average magnitude of the sidelobes 360 of the autocorrelation function xcex9xcex1345 of the finite-length beacon packet typically reaches a maximum near the midpoint of the sidelobes 360. Roughly, the sidelobes 360 have an average magnitude of ✓N at time t=tb/2. It should be noted that, for large values of N, the magnitudes of the values in the sidelobes is exaggerated relative to the magnitude of the peak in FIG. 4B.)
The reception procedure for an exemplary receiver is depicted in FIG. 4A. (For convenience of depiction only four reception bins are depicted in FIG. 4A. However, receivers will typically use more than four reception bins per reception time window.) The internally-generated code sequences 315a.1, 315a.2 and 315a.3 for the first time bin for three reception events 341, 342 and 343 are depicted on a first reception time axis 321, the internally-generated code sequences 315b.1, 315b.2 and 315b.3 for the second time bin for the three reception events 341, 342 and 343 are depicted on a second reception time axis 322, and so on. In the first reception event 341 beginning at time t0 the receiver generates a first internally-generated code sequence 315a.1 of length tb, i.e., the length of the anticipated beacon packet 310. The received signal, i.e., the signal 300 broadcast by the transmitter, is multiplied with the internally-generated code sequence 315a.1 and integrated over time. In this case since there is no beacon packet 310 arriving at the receiver beginning at time t0, so the result of the multiplication and integration produces a relatively small value, which is only non-zero due to received noise. The receiver will therefore determine that a beacon packet 310 is not arriving at the receiver beginning at that time. Also, during the first reception event 341 the receiver generates a second internally-generated code sequence 315b.1 of length tb beginning at time [t0+(tw/3)]. The received signal 300 is multiplied with the internally-generated code sequence 315b.1 and integrated over time. Again, the receiver will determine that no beacon packet 310 is arriving at the receiver beginning at that time since the value produced by the integration is relatively small. Similarly, during the first reception event 341 the receiver generates a third and fourth internally-generated code sequences 315c.1 and 315d.1 beginning at times [t0+(2tw/3)] and [t0+tw] and performs multiplications and time integrations, and will determine that a beacon packet 310 did not arrive beginning at those times either.
Since the time-integrating correlator can only perform one set of measurements per cycle time tc, the beacon signal is searched for by incrementing the starting time of the time window 315 by tc+tw and performing another reception. In particular, in the second reception event 342 beginning at time t0+tc+tw the receiver generates a first internally-generated code sequence 315a.2 of length tb which is multiplied with the received signal 300 and integrated over time. Since, in this case there is no beacon packet 310 arriving at the receiver beginning at time t0+tc+tw, the result of the multiplication and integration produces a relatively small value, and the receiver determines that a beacon packet 310 is not arriving at the receiver beginning at that time t0+tc+tw. Similarly, during the second reception event 342 the receiver generates a second, third and fourth internally-generated code sequences 315b.2, 315c.2, and 315d.2 of length tb beginning at times [t0+tc+(tw/3)], [t0+tc+(2tw/3)], and [t0+tc,+tw], respectively. The received signal 300 is multiplied with the internally-generated code sequences 315b.2, 315c.2, and 315d.2 and integrated over time and, again, the receiver will determine that no beacon packet 310 is arriving at the receiver beginning at those times since the value produced by the integration is relatively small. The beacon signal is searched for by incrementing the starting time of the time window 315 by an additional tc+tw and performing another reception 343, and so on.
Therefore, on average the contact time, i.e., the time required for the receiver to locate the beacon signal, will take the transceiver xc2xdxc2x7(tc/tw) cycle times to locate a beacon packet 310. If the cycle time tc is approximately one millisecond, and the time windows have a length tw of around 100 nanoseconds, then it will require approximately 10,000 cycles (ie., on the order of ten seconds) for the transceiver to locate a beacon packet 310. The ten seconds required for the initial stage of the acquisition process is a perceptible length of time by human standards, and it would be desirable to provide improved methods of acquisition which would require less time to perform.
Therefore, it is an object of the present invention to provide a system for rapid acquisition by spread spectrum transceivers.
It is another object of the present invention to provide a system for rapid acquisition by spread spectrum transceivers with finite length reception windows.
It is another object of the present invention to provide a system for rapid acquisition by spread spectrum transceivers using an episodic beacon signal.
It is another object of the present invention to provide a system for rapid acquisition by spread spectrum transceivers using a prearranged beacon signal.
It is another object of the present invention to provide a system which can rapidly perform the contact stage of the acquisition process.
It is another object of the present invention to provide a system which can rapidly perform the synchronization stage of the acquisition process.
Another object of the present invention is to provide a transceiver which broadcasts a beacon signal which has low cross-correlations with code sequences used by other transceivers, where these other transceivers are possibly within the network of transceivers which may communicate with the first transceiver.
Another object of the present invention is to provide a beacon packet which has an autocorrelation function with sidelobes which have a significant time span and are of significant size.
Another object of the present invention is to provide a beacon packet which has an autocorrelation function that has sidelobes with a structure that allows sampling thereof to provide an estimate of the location of the peak of the autocorrelation function.
Furthermore, it is an object of the present invention to provide a transceiver which broadcasts a beacon signal which has low cross-correlations with code sequences used by other transceivers, and which has an autocorrelation function with sidelobes which have a significant time span, are of significant size, and have a structure that allows sampling thereof to provide an estimate of the location of the peak of the autocorrelation function.
In addition, other objects, features and advantages of the present invention will become apparent from the following detailed description when taken in conjunction with the accompanying drawings.
The present invention is directed to a method for two spread spectrum transceivers to perform signal acquisition in the vicinity of a number of additional spread spectrum transceivers which communicate with each other using a class of code sequences which have low cross-correlations and auto-correlations with small off-peak values. A first one of the two spread spectrum transceivers transmits a beacon signal consisting of beacon packets which are transmitted at regularly spaced times separated by a beacon cycle interval. The length of the beacon packets is shorter than the beacon cycle interval so that there is a period of nontransmission between each of the beacon packets. The beacon packets have an acyclic auto-correlation function with sidelobes that are not small relative to a peak value of the acyclic auto-correlation function, and these sidelobes have a structure which allows a sampling of a number of sidelobe values to be used to provide an estimate of a location of the peak of the acyclic auto-correlation.
If the second spread spectrum transceiver fails to receive a beacon packet during a reception window, the second spread spectrum transceiver attempts a reception during a subsequent reception window which begins at a time which is an integer multiple of said beacon cycle interval plus or minus roughly the beacon packet length later than the beginning of the previous reception attempt. Attempted receptions are performed by calculation of correlations between time delayed versions of an internally-generated beacon packet and the received signal.
Once the second transceiver receives a beacon packet during a reception window (ie., the first successful reception window), the second transceiver performs a reception during a reception window which begins at a time which is an integer multiple of the beacon cycle interval plus or minus a fraction of twice the beacon packet length later than the beginning of the first successful reception window.
However, if the second transceiver fails to receive some portion of a beacon packet during that reception window, the second transceiver performs another reception during a reception window which begins at a time which is an integer multiple of the beacon cycle interval minus or plus, respectively, that fraction of twice the beacon packet length later than the beginning of the first successful reception window.
The time (modulo the cycle time) at which the beacon packets are transmitted by the first transceiver is determined by estimating the location of the maximum of the correlation function between the delayed internally-generated beacon packets and the received beacon packets based on the times and values of the successful receptions of beacon packets by the second transceiver.